#include <iostream>
#include <tuple>
using namespace std;
template<typename T, size_t n>
tuple<T, int, int> MaxArrSub_X(T(*arr)[n], int low, int mid, int height)
{
	T leftSum = 0;//这里最好是趋于无限小
	T sum = 0;
	int l = 0;
	for (int i = mid; i > low; --i)
	{
		sum += (*arr)[i];
		if (sum > leftSum)
		{
			leftSum = sum;
			l = i;
		}
	}

	sum = 0;
	T rightSum = 0;//同理
	int r = 0;
	for (int i = mid + 1; i < height; ++i)
	{
		sum += (*arr)[i];
		if (sum > rightSum)
		{
			rightSum = sum;
			r = i;
		}
	}

	return tuple<T, int, int>(rightSum + leftSum, l, r);
}

template<typename T, size_t n>
tuple<T, int, int> MaxArrSub(T(*arr)[n], int low = 0, int height = n)
{
	if (low == height)
		return tuple<T, int, int>((*arr)[low], low, height);

	int mid = (height + low)/2;
	tuple<T, int, int> leftMax = MaxArrSub(arr, low, mid);
	tuple<T, int, int> rightMax = MaxArrSub(arr, mid + 1, height);
	tuple<T, int, int> centerMax = MaxArrSub_X(arr, low, mid, height);

	if (leftMax >= rightMax && leftMax >= centerMax)
		return leftMax;
	else if (rightMax >= leftMax && rightMax >= centerMax)
		return rightMax;
	else
		return centerMax;
}

int main()
{
	int arr1[] = { -7, -25, -5, -9, -3, -5, -1 };

	tuple<int, int, int> Date = MaxArrSub(&arr1, 0, 7);

	return 0;
}
